1. Field of Invention
This invention relates generally to imaging processing and more particularly to color image quantization technology.
2. Description of the Prior Art
The present invention concerns the technology of image output to a video display or to a printer. In most cases, a digitally stored color image is stored in terms of nominal values that a device outputting the image should attempt to approximate as closely to the original source as possible. The image may be stored as pixels wherein the pixels are typically presented in the form of a three-component vectors. Quantizing or dithering an image is a process of reducing bit-resolution of a source image. Image quantization or dithering can be done through either error-diffusion or dither matrix, which is also known as the threshold array method.
Conventionally, quantizing or dithering a red-green-blue (RGB) or cyan-magenta-yellow (CMY) color image is done by quantizing each colorant separately through multiple independent dither matrices. The method is simple to implement, but at a cost of local color variation and the complexity of providing multiple independent dither matrixes.
Referring to FIG. 1, which illustrates a prior art schematic view of a source color space 10 of a color image. The color space 10 is presented as a three-dimensional vector space defined by three axes A 12, B 14 and C 16 which correspond to colorants R, G, B or C, M, Y respectively depending on the output device. A pixel value is a three-component vector having a point in the color space. A color image is a two-dimensional array of pixel values. A source image contains a source color image. An output image for display or printout contains an output color image. Each pixel in the source image is referred to by Pixel[i,j], wherein i and j are indices into the pixel array. The pixel values of colorants in the source image are referred to as As[i,j] 18, Bs[i,j] 20, Cs[i,j] 22 respectively. The values of each colorant are integers encoded in S-bits, which means 0<=As[i,j], Bs[i,j], Cs[i,j]<2S.
FIGS. 2A, 2B and 2C are diagrams showing a prior art method for dithering a source image. The color image is to be dithered into a 3-colorant pixel array with colorant values encoded in T-bits, wherein T<=S. Prior to dithering the source image, the S-bits source colorant values As[i,j], Bs[i,j] and Cs[i,j] are converted to higher bit-resolution encoded in U-bits, where U>=S, through three linearization look-up tables La 24, Lb 25 and Lc 26 for one or more of the following purposes: linearization, gray balance, and preserving numerical precision. The converted U-bits colorant values are in a quantization space (0, 2U). The converted three colorant values in the quantization space are denoted by Aq[i,j] 27, Bq[i,j] 28 and Cq[i,j] 29. As shown in FIGS. 2A, 2B and 2C, three quantization table At[t1] 30, Bt[t2] 31 and Ct[t3] 32 for each colorant A, B, C respectively are defined, where 0<=t1, t2, t3<2T. The values of At[t1], Bt[t2], and Ct[t3] are U-bit numbers in the quantization space. This means 0<=At[t1], Bt[t2], Ct[t3]<2U, and At[t1], Bt[t2], Ct[t3] are selected from the 2U possible values and satisfying At[0]=0, Bt[0]=0, Ct[0]=0; At[t1]<At[t1+1], Bt[t2]<Bt[t2+1], Ct[t3]<Ct[t3+1]. It is desirable, but not required, to have a equally divided quantization space, that is for all the possible values of a and b, (At[a+1]−At[a])=(At[b+1]−At[b]), (Bt[a+1]−Bt[a])=(Bt[b+1]−Bt[b]) and (Ct[a+1]−Ct[a])=(Ct[b+1]−Ct[b]). The indices t1 36, t2 37 and t3 38 which are indices of the three quantization tables are also the output pixel value in the output color space.
FIG. 3 is a diagram showing a prior art schematic view of a 3-dimensional cubic quantization interval 40 containing the converted pixel value (Aq[i,j], Bq[i,j], Cq[i,j]) 41 in the quantization space 42. The entire quantization space are divided into smaller cubic subintervals by the three quantization tables At[ ], Bt[ ] and Ct[ ]. As shown in FIG. 4, which is a diagram illustrating a prior art schematic view of a cubic quantization interval, having 8 corner points P000=At[t1]Bt[t2]Ct[t3] 44, P100=At[t1+1]Bt[t2]Ct[t3] 46, P010=At[t1]Bt[t2+1]Ct[t3] 48, P110=At[t1+1]Bt[t2+1]Ct[t3] 50, P001=At[t1]Bt[t2]Ct[t3+1] 52, P101=At[t1+1]Bt[t2]Ct[t3+1] 54, P011=At[t1]Bt[t2+1]Ct[t3+1] 56, P111=At[t1+1]Bt[t2+1]Ct[t3+1] 58.
A dither matrix, or threshold array is an two dimensional array of uniformly distributed random or pseudo-random numbers H[i,j], where 0<=H<=Hmax. If the quantization space is equally divided, Hmax equals to (At[t1+1]−At[t1]), (Bt[t2+1]−Bt[t2]) and (Ct[t3+1]−Ct[t3]).
For each pixel in the color image, the goal of the dithering process is to select one out of the eight corner points P000, P100, . . . , P111 of the cubic quantization interval 40 containing the converted pixel value 41 in the quantization color space 42, by comparing a value from the threshold array against the relative offset of the pixel value in the quantization interval. The output pixel value of the dithering process is three quantization table indices t1, t2 and t3 corresponding to the selected corner point.
The above-described conventional method of quantizing or dithering an image requires three independent dither matrices for each of the three colorants to process the source image. The result of this methodology tends to generate color with higher variation. It is, therefore, desirable to have a method that can efficiently dither an image with a single dither matrix yet still be able to retain the quality of such image.